package com.sjf.day02.tree.ThreadBinaryTree;

import cn.hutool.Hutool;
import cn.hutool.core.util.ObjectUtil;
import com.sjf.day02.AnnoTest.NodeType;
import org.jetbrains.annotations.NotNull;
import sun.reflect.generics.tree.Tree;

import java.lang.reflect.Field;

/**
 * 线索化二叉树
 *
 * @author <huangtang>
 * @since 2022/1/6 14:28
 **/
public class ThreadBinaryTreeDemo {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(8);
        TreeNode node5 = new TreeNode(10);
        TreeNode node6 = new TreeNode(14);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
        threadBinaryTree.root = root;
        //threadBinaryTree.threadedNodes();
        //threadBinaryTree.threadedList();
        //threadBinaryTree.threadedprevNodes();
        //threadBinaryTree.threadedprevList();
        threadBinaryTree.threadedpostNodes();
        threadBinaryTree.threadedpostList();
        //threadBinaryTree.midOrder();
        //System.out.printf("%s  %s",node5.left,node5.right);
    }

}

/**
 * 线索化的二叉树
 */
class ThreadBinaryTree{

    public TreeNode root; //根节点

    //为了实现线索化，需要创建指向当前节点的前驱节点的指针
    public TreeNode prev; //前驱节点

    public int size;//节点个数

    public void threadedpostNodes(){
        this.threadedprevNodes(root);
    }

    /**
     * 线索化后序遍历
     * @param node
     */
    public void threadedpostNodes(TreeNode node){
        if(ObjectUtil.isNull(node)){
            return;
        }
        //线索化左子树
        if(node.leftType == 0){
            threadedpostNodes(node.left);
        }
        //线索化右子树
        if(node.rightType == 0){
            threadedpostNodes(node.right);
        }
        //线索化当前节点
        //先处理当前节点的前驱节点
        if(ObjectUtil.isNull(node.left)){
            node.left = prev; //当前节点的左指针指向前驱节点
            node.leftType = 1; //修改左指针类型为1，指向前驱节点
        }
        //处理后继节点
        if(ObjectUtil.isNotNull(prev) && ObjectUtil.isNull(prev.right)){
            prev.right = node;//让前驱节点的右指针指向node
            prev.rightType = 1;//指针类型修改为1
        }
        prev = node; //让prev跟着node走

    }

    /**
     * 后序遍历线索化二叉树
     */
    public void threadedpostList(){
        TreeNode node = root;
        while(node!=null){
            //先找到leftType为1的节点
            while(ObjectUtil.equal(node.leftType,0)){
                //System.out.println(node);
                node = node.left;
            }
            //如果当前节点的右指针指向的是后继节点，则一直打印
            while(ObjectUtil.equal(node.rightType,1)){
                System.out.println(node);
                prev = node;
                node = node.right;
            }
            if(node == root){
                System.out.println(node);
                return;
            }
            while(node!=null && node.right==prev){
                System.out.println(node);
                prev = node;
                node = node.right;
            }
            System.out.println(node);//打印当前节点
            //替换遍历的节点
            node = node.right;
        }
    }

    public void threadedprevNodes(){
        this.threadedprevNodes(root);
    }

    /**
     * 线索化前序遍历
     * @param node
     */
    public void threadedprevNodes(TreeNode node){
        if(ObjectUtil.isNull(node)){
            return;
        }

        //线索化当前节点
        //先处理当前节点的前驱节点
        if(ObjectUtil.isNull(node.left)){
            node.left = prev; //当前节点的左指针指向前驱节点
            node.leftType = 1; //修改左指针类型为1，指向前驱节点
        }
        //处理后继节点
        if(ObjectUtil.isNotNull(prev) && ObjectUtil.isNull(prev.right)){
            prev.right = node;//让前驱节点的右指针指向node
            prev.rightType = 1;//指针类型修改为1
        }
        prev = node; //让prev跟着node走
        //线索化左子树
        if(node.leftType == 0){
            threadedprevNodes(node.left);
        }
        //线索化右子树
        if(node.rightType == 0){
            threadedprevNodes(node.right);
        }
    }

    /**
     * 前序遍历线索化二叉树
     */
    public void threadedprevList(){
        TreeNode node = root;
        while(node!=null){
            //先找到leftType为1的节点
            while(ObjectUtil.equal(node.leftType,0)){
                System.out.println(node);
                node = node.left;
            }
            //如果当前节点的右指针指向的是后继节点，则一直打印
            while(ObjectUtil.equal(node.rightType,1)){
                System.out.println(node);
                node = node.right;
            }
            System.out.println(node);//打印当前节点
            //替换遍历的节点
            node = node.right;
        }
    }


    public void threadedNodes(){
        this.threadedNodes(root);
    }
    /**
     * 对二叉树的中序遍历进行线索化
     */
    public void threadedNodes(TreeNode node){
        if(ObjectUtil.isNull(node)){
            return;
        }
        //线索化左子树
        threadedNodes(node.left);
        //线索化当前节点
        //先处理当前节点的前驱节点
        if(ObjectUtil.isNull(node.left)){
            node.left = prev; //当前节点的左指针指向前驱节点
            node.leftType = 1; //修改左指针类型为1，指向前驱节点
        }
        //处理后继节点
        if(ObjectUtil.isNotNull(prev) && ObjectUtil.isNull(prev.right)){
            prev.right = node;//让前驱节点的右指针指向node
            prev.rightType = 1;//指针类型修改为1
        }
        prev = node; //让prev跟着node走
        //线索化右子树
        threadedNodes(node.right);
    }

    /**
     * 中序遍历线索化二叉树
     */
    public void threadedList(){
        TreeNode node = root;
        while(node!=null){
            //先找到leftType为1的节点
            while(ObjectUtil.equal(node.leftType,0)){
                node = node.left;
            }

            System.out.println(node);//打印当前节点
            //如果当前节点的右指针指向的是后继节点，则一直打印
            while(ObjectUtil.equal(node.rightType,1)){
                System.out.println(node.right);
                node = node.right;
            }
            //替换遍历的节点
            node = node.right;
        }
    }

    public int getSize() {
        return numberOfTree(root);
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        if(root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 前序查找
     * @param id 查找的id
     */
    public void preOrderSearch(int id){
        if(root!=null){
            TreeNode treeNode = this.root.preOrderSearch(id);
            if(treeNode == null){
                System.out.println("未找到节点");
            }
        }else{
            System.out.println("二叉树为空，无法查找");
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(root!=null){
            this.root.midOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 中序查找
     * @param id 查找的id
     */
    public void midOrderSearch(int id){
        if(root!=null){
            TreeNode treeNode = this.root.midOrderSearch(id);
            if(treeNode == null){
                System.out.println("未找到节点");
            }
        }else{
            System.out.println("二叉树为空，无法查找");
        }
    }

    /**
     * 后序遍历
     */
    public void AfterOrder(){
        if(root!=null){
            this.root.AfterOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 后序查找
     */
    public void AfterOrderSearch(int id){
        if(root!=null){
            TreeNode treeNode = this.root.AfterOrderSearch(id);
            if(treeNode == null){
                System.out.println("未找到节点");
            }
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 删除节点
     * @param id 节点id
     */
    public void delNode(int id){
        if(root!=null){
            //先判断root是否是删除节点
            if(root.id == id){
                root = null;
            }else{
                root.delNode(id);
            }
        }else {
            System.out.println("树为空，无法删除");
        }
    }

    /**
     * 获取树节点的个数
     * @param treeNode 当前节点
     * @return 当前节点下的子节点个数
     */
    public int numberOfTree(TreeNode treeNode){
        if(treeNode==null){
            return size;
        }
        size++;
        //递归左遍历
        if(treeNode.left!=null){
            numberOfTree(treeNode.left);
        }
        if(treeNode.right!=null){
            numberOfTree(treeNode.right);
        }
        return size;
    }

}


class TreeNode{
    public int id;
    public TreeNode left;
    public TreeNode right;
    @NodeType(value = 1)
    public int leftType; // 0表示是左子树 1表示前驱节点
    @NodeType(value = 1)
    public int rightType;// 0表示是右子树 1表示后继节点


    public  static int count1;//比较次数
    public  static int count2;//比较次数
    public  static int count3;//比较次数

    public TreeNode(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "id=" + id +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        //先输出父节点
        System.out.println(this);
        //递归左子树
        if(this.left!=null){
            this.left.preOrder();
        }
        //递归右子树
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    /**
     * 前序查找
     */
    public TreeNode preOrderSearch(int id){
        count1++;
        if(this.id == id){
            System.out.println("找到节点"+this);
            System.out.println("比较次数"+count1);
            return this;
        }
        if(this.left!=null){
            //递归左子树
            this.left.preOrderSearch(id);
        }
        if(this.right!=null){
            //递归右子树
            this.right.preOrderSearch(id);
        }
        return null;
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        //先递归左子树
        if(this.left!=null){
            this.left.midOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归右子树
        if(this.right!=null){
            this.right.midOrder();
        }
    }

    /**
     * 中序查找
     */
    public TreeNode midOrderSearch(int id){
        if(this.left!=null){
            this.left.midOrderSearch(id);
        }
        count2++;
        if(this.id == id){
            System.out.println("找到节点"+this);
            System.out.println("比较次数"+count2);
            return this;
        }
        if(this.right!=null){
            this.right.midOrderSearch(id);
        }
        return null;
    }

    /**
     * 后序遍历
     */
    public void AfterOrder(){
        if(this.left!=null){
            this.left.AfterOrder();
        }
        if(this.right!=null){
            this.right.AfterOrder();
        }
        System.out.println(this);
    }

    /**
     * 后序查找
     */
    public TreeNode AfterOrderSearch(int id){
        if(this.left!=null){
            this.left.AfterOrderSearch(id);
        }
        if(this.right!=null){
            this.right.AfterOrderSearch(id);
        }
        count3++;
        if(this.id == id){
            System.out.println("找到节点"+this);
            System.out.println("比较次数:"+count3);
            return this;
        }
        return null;
    }

    /**
     * 删除节点
     * @param id 节点id
     */
    public void delNode(int id){
        if(this.left!=null && this.left.id == id){
            //删除左子节点即可
            this.left = haveChild(this.left);
            return;
        }
        if(this.right!=null && this.right.id == id){
            this.right = haveChild(this.right);
            return;
        }
        //递归左子节点删除
        if(this.left!=null){
            this.left.delNode(id);
        }
        //递归右子节点删除
        if(this.right!=null){
            this.right.delNode(id);
        }
    }

    /**
     * 不删除子树的方法
     * @param treeNode 返回删除节点后顶替该节点的节点
     * @return
     */
    public TreeNode haveChild(@NotNull TreeNode treeNode){
        //没有字节点直接删除
        if(treeNode.left == null && treeNode.right == null){
            return null;
        }
        //如果有一个节点，则让该节点顶替
        if(treeNode.left == null){
            return treeNode.right;
        }else if(treeNode.right == null){
            return treeNode.left;
        }
        //有两个节点则，则让左节点顶替
        treeNode.left.right = treeNode.right;
        return treeNode.left;
    }
}